import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Title: Dijkstra求最短路堆优化
 * @Author 贾金博
 * @Package PACKAGE_NAME
 * @Date 2024/3/15 17:00
 * @description:
 */
public class Dijkstra求最短路堆优化 {
    public static final int N = 200010;
    public static Scanner sc = new Scanner(System.in);
    public static int[] dis = new int[N];
    public static boolean st[] = new boolean[N];
    public static int[] h = new int[N];
    public static int[] ne = new int[N];
    public static int[] w = new int[N];
    public static int[] e = new int[N];
    public static int idx = 0;
    public static int n = 0;
    public static int m = 0;
    public static Queue<pair> q = new PriorityQueue();

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1; i <= n; ++ i ) {
            dis[i] = 0x3f3f3f;
            h[i] = -1; // 记得初始化
        }


        for(int i = 1; i <= m; ++ i ) {
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            add(a, b, c);
        }

        dijkstra();
        System.out.println(dis[n] >= 0x3f3f3f ? -1 : dis[n]);

    }

    public static void dijkstra() {
        q.add(new pair(1, 0));
        dis[1] = 0;
        while(!q.isEmpty()) {
            pair t = q.poll();
            int ver = t.getVer();
            int dist = t.getDist();
            if(st[ver]) {
                continue;
            }
            st[ver] = true;
            for(int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if(dis[j] > dist + w[i]) {
                    dis[j] = dist + w[i];
                    q.add(new pair(j, dis[j]));
                }
            }
        }
    }

    public static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++ ;
    }

}

class pair implements Comparable<pair>{

    private int ver;
    private int dist;

    public pair() {
    }

    public pair(int ver, int dist) {
        this.ver = ver;
        this.dist = dist;
    }

    /**
     * 获取
     * @return ver
     */
    public int getVer() {
        return ver;
    }

    /**
     * 设置
     * @param ver
     */
    public void setVer(int ver) {
        this.ver = ver;
    }

    /**
     * 获取
     * @return dist
     */
    public int getDist() {
        return dist;
    }

    /**
     * 设置
     * @param dist
     */
    public void setDist(int dist) {
        this.dist = dist;
    }

    public String toString() {
        return "pair{ver = " + ver + ", dist = " + dist + "}";
    }

    @Override
    public int compareTo(pair o) {
        return this.dist - o.dist;
    }
}
